/********************************************************************************************
* Copyright (c) 2011, Matthew McMullan, Jorel Lalicki and Mike Heise, Jorel Lalicki and Mike Heise, Jorel Lalicki                                       *
* All rights reserved.                                                                      *
*                                                                                           *
* Redistribution and use in source and binary forms, with or without modification, are      *
* permitted provided that the following conditions are met:                                 *
*                                                                                           *
* Redistributions of source code must retain the above copyright notice, this list of       *
* conditions and the following disclaimer.                                                  *
*                                                                                           *
* Redistributions in binary form must reproduce the above copyright notice, this list of    *
* conditions and the following disclaimer in the documentation and/or other materials       *
* provided with the distribution.                                                           *
*                                                                                           *
* Neither the name of the Adaptive Game Math Library nor the names of its contributors may  *
* be used to endorse or promote products derived from this software without specific prior  *
* written permission.                                                                       *
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY       *
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF   *
* MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL    *
* THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,      *
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT  *
* OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) *
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR  *
* TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS        *
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.                              *
********************************************************************************************/

#ifndef __agml_chunks_h__
#define __agml_chunks_h__

#include "pages.h"

// todo: return memory to the OS
namespace agml {
	namespace _memory {
		struct spacer {
			u8 space[16];
		};
		struct _memchunk {
			_memchunk *next;
			u32_fast size;
		};
		class _chunk_allocator {
		protected:
			_memchunk *chunks;
			_memchunk *getNewPage() {
				_memchunk *page;
				page = (_memchunk *) page_allocator.alloc(2);
				page->next = 0;
				page->size = page_allocator.getPageSize()/16;
				unused += page->size;
				return page;
			}
			void garbage_collect() {
				_memchunk *i = chunks, *j = 0;
				uptr tmp;
				while (i!=0 && unused>page_size*8) {
					while (i!=0 && i->size < page_size) {
						j = i;
						i = i->next;
					}
					if (i==0) break;
					tmp = (uptr)i/16;
					tmp/= page_size;
					if (tmp*page_size*16 == (uptr)i) {
						if (i->size % page_size == 0) {
							unused -= i->size;
							j->next = i->next;
						} else {
							j->next = (_memchunk *)((uptr)i+(i->size/page_size)*page_size*16);
							j->next->next = i->next;
							j->next->size = i->size%page_size;
						}
						page_allocator.free(i,i->size/page_size);
						i=j->next;
					}
				}
			}
			bool tryJoin(_memchunk *chunk) {
				if ((uptr)chunk + chunk->size*16 == (uptr)chunk->next) {
					chunk->size += chunk->next->size;
					chunk->next = chunk->next->next;
					tryJoin(chunk);
					return true;
				}
				return false;
			}
			u32 used, unused, page_size;
		public:
			_chunk_allocator() {
				chunks = 0;
				used = unused = 0;
				page_size = page_allocator.getPageSize()/16;
			}
			template<typename t> void alloc(t *&target) {
				target = (t*)alloc((sizeof(t)+15)/16);
			}
			template<typename t> void free(t *&target) {
				free(target,(sizeof(t)+15)/16);
				target = 0;
			}
			void *alloc(u32 number) {
				// seek to a large enough chunk
				_memchunk *i = chunks, *j = 0, *chunk;
				while (i!=0 && i->size < number) {
					j = i;
					i = i->next;
				}
				// allocate new memory if needed
				if (i==0) {
					i = getNewPage();
					if (j!=0) {
						j->next = i;
					} else {
						chunks = i;
					}
				}
				// pull a chunk out from the selected area
				chunk = i;
				if (j!=0) {
					if (i->size > number) {
						j->next = (_memchunk *)(((uptr)i)+number*16);
						j->next->next = i->next;
						j->next->size = i->size-number;
					} else {
						j->next = i->next;
					}
				} else {
					if (i->size > number) {
						chunks = (_memchunk *)(((uptr)i)+number*16);
						chunks ->next = 0;
						chunks ->size = i->size-number;
					} else {
						chunks = 0;
					}
				}
				used += number;
				unused -= number;
				return chunk;
			}
			void free(void *chunk, u32 number) {
				if (!number || !chunk) return;
				// seek to the proper location
				_memchunk *i=chunks, *j=0;
				while (chunk < i) {
					j = i;
					i = i->next;
				}
				// consolidate and insert
				if (j) {
					j->next = (_memchunk *)chunk;
					((_memchunk *)chunk)->next = i;
					((_memchunk *)chunk)->size = number;
					if (!tryJoin(j)) {
						tryJoin((_memchunk *)chunk);
					}
				} else if (i) {
					chunks = (_memchunk *)chunk;
					chunks->next = i;
					chunks->size = number;
				} else {
					chunks = (_memchunk *)chunk;
					chunks->next = 0;
					chunks->size = number;
				}
				// update internal state
				used -= number;
				unused += number;
				garbage_collect();
			}
		};
	}
	_memory::_chunk_allocator chunk_allocator;
}

#endif
